// run: $exec < input
// opt: 0
// flag: -g
#include <cstdio>
#include <cstring>

long long const mo = 1000000007;
int const maxn = 200007;
char s[maxn], t[maxn];
long long dp[maxn];
int next[maxn];

void get_next()
{
	next[0] = -1;
	int i = 0, j = -1;
	while(t[i] != '\0')
	{
		if(j == -1 || t[i] == t[j])
		{
			i ++;
			j ++;
			next[i] = j;
		}
		else
			j = next[j];
	}
}

long long KMP()
{
	get_next();
	std::memset(dp, 0, sizeof(dp));
	int i = 0, j = 0, len = strlen(t);
	dp[0] = 1;
	while (s[i]) {
		if(j == -1 || s[i] == t[j]) {
			i++; j++;
			dp[i] = dp[i - 1];
		} else
			j = next[j];

		if (j == len) {
			j = next[j];
			dp[i] = (dp[i] + dp[i - len]) % mo;
		}
	}
	int n = strlen(s);
	return dp[n];
}

int main()
{
	int T; scanf("%d", &T);
	for (int ti = 1; ti <= T; ti++) {
		scanf("%s %s", s, t);
		printf("Case #%d: %lld\n", ti, KMP());
	}
}

